package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-11 11:20
 **/
public class LeetCode209 {

    /**
     * 暴力破解法
     * @param target
     * @param nums
     * @return
     */
    /*public int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        //看了官方的代码，又优化了一下
        int len = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum >= target) {
                return 1;
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    //这里模仿了官方的代码，当第一次有符合条件的，len必为j-i+1
                    len = Math.min(len, j - i + 1);
                    break;
                }
            }
        }
        //当len == Integer.MAX_VALUE时，说明这个target大于数组中所有值的和，target不存在
        return len == Integer.MAX_VALUE ? 0 : len;
    }
*/
    /**
     * 自己写了一遍前缀和+二分查找
     */
    public int minSubArrayLen3(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        //sums数组用来存储前缀和
        int[] sums = new int[n + 1];
        //sums[0] = 0表示前0个元素的和为0
        //sums[i]表示前i的元素的和
        sums[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            //前i个元素的前缀和 = 前i-1个元素的前缀和+nums[i-1]
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int len = Integer.MAX_VALUE;
        int target2;
        for (int i = 1; i <= nums.length; i++) {
            target2 = sums[i - 1] + target;
            //这里使用工具类中的二分查找,这个bound返回的是-(low + 1)
            int bound = Arrays.binarySearch(sums, target2);
            //首先如果这个bound小于0的话，说明数组中不存在等于target2的值，先将其转成正常的边界，由于我们这个题在前缀和大于target2的情况也是满足题意的，
            // 所以最好还是自己写一个二分查找，比较好理解一点，看官方的代码理解了好久
            if (bound < 0) {
                bound = - bound - 1;
            }

            if (bound <= n) {
                //这里的bound - i + 1就是满足条件的最小子数组的长度，需要理解一下，最好就是自己代一个数组进入debug一下
                len = Math.min(bound - i + 1, len);
            }

        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    /**
     * 官方写的前缀和+二分法
     * @param target
     * @param nums
     * @return
     */
    /*public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target2 = target + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target2);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;

    }*/

    /**
     * 看了滑动窗口解法写的代码
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        //指针2
        int start = 0;
        //指针1
        int end = 0;
        //保存子数组的最小长度
        int len = Integer.MAX_VALUE;
        //用来维护nums[start]到nums[end]的和
        int sum = 0;
        //循环判断end
        while (end < n) {
            sum += nums[end];
            //sum>target，给len赋值，然后减去nums[start],start右移，寻找最小长度的子数组
            while (sum >= target) {
                len = Math.min(len, end- start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }

        return len == Integer.MAX_VALUE ? 0 : len;
    }

    public static void main(String[] args) {
        //int[] nums = {2, 3, 1, 2, 4, 3};
        int[] nums = {1, 2, 3, 4, 5};
        LeetCode209 code = new LeetCode209();
        System.out.println(code.minSubArrayLen(16, nums));
    }
}
